package com.zk.algorithm.math;

import com.zk.algorithm.Utils;
import com.zk.algorithm.annotation.Easy;
import com.zk.algorithm.annotation.LeetCodeExplore;
import com.zk.algorithm.annotation.TiaoZhanChengXuSheJiJingSai;

/**
 * 前 n (不包括 n) 个数中有多少个素数
 *
 * @author zk
 */
@LeetCodeExplore
@Easy
@TiaoZhanChengXuSheJiJingSai("素数的个数")
public class CountPrimes {

    // [ ,2, ,4, ,6, ,8, ,10]
    // [ ,2,3,4, ,6, ,8,9,10]
    // [ ,2,3,4,5,6, ,8,9,10]
    // [ ,2,3,4,5,6,7,8,9,10]
    public int countPrimes(int n) {
        int count = 0;
        boolean[] notPrimesArray = new boolean[n];

        // 易错点
        //               小于
        //                ↓
        for (int i = 2; i < n; i++) {
            // 是素数
            if (!notPrimesArray[i]) {
                count++;
                markNonePrimeNumbers(n, notPrimesArray, i);
            }
        }

        return count;
    }

    /**
     * 标记非素数
     *
     * 一个素数的 2、3、4、5、... 倍都不是素数
     *
     * @param n
     * @param notPrimesArray
     * @param i 代表素数
     */
    private void markNonePrimeNumbers(int n, boolean[] notPrimesArray, int i) {
        int j = 2;
        int tmp = 1;

        // 易错点
        //
        // 迈多大的步子: i * j 步
        //              ↓
        //
        //                  小于
        //                   ↓
        while ((tmp = i * j) < n) {
            notPrimesArray[tmp] = true;
            j++;
        }
    }

    public static void main(String...args) {
        Utils.println(new CountPrimes().countPrimes(7));
        Utils.println(new CountPrimes().countPrimes(10));
    }

}
